﻿#include <stdio.h>
#include <conio.h>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <math.h>

#include <string>
#include <fstream>

using namespace std;
//======================================================================================================
struct NST
{
	char BitString[8];
	int RealValue;
	int Fitness;
	NST(){}

	NST(const NST & _NST)
	{
		for(int i=0;i<8;i++)
			BitString[i] = _NST.BitString[i];
		RealValue = _NST.RealValue;
		Fitness = _NST.Fitness;
	}

	NST(char _BitString[],int _RealValue,int _Fitness)
	{
		for(int i=0;i<8;i++)
			BitString[i] = _BitString[i];
		RealValue = _RealValue;
		Fitness = _Fitness;
	}
};
//======================================================================================================
void ReadInput(string);
void WriteOuput(string);
//======================================================================================================
int GetRealValueFromBitString(char _BitString[]);//chuyển từ chuỗi nhị phân về số thập phân
NST GetNSTFromRealValue(int);//từ một realvalue tạo ra một NST tương ứng
void UpdateFitness(NST);
//======================================================================================================
void Init(void);//hàm khởi tạo quần thể ban đầu
void Crossover();//hàm lai ghép
void SubCrossover(int,int);
void Multation(NST);//hàm đột biến
void SubMultation(NST);
void Update_QuanThe(vector<NST>);
void UpdateFitness();
int Result();
void Fitness_GiamDan();
//======================================================================================================
int NumberLoop = 50;//số lần lặp
int MaxValue = 10000;//Giới hạn lớn nhất
int PopSize = 20;//kích thước quần thể
float Pcrossover = 0.9;//tỉ lệ lai
float Pmultation = 0.05;//tỉ lệ đột biến
//======================================================================================================
vector<NST> QuanThe(0);//Quần thể
vector<NST> temp(0);//Quần thể tạm mới
int a = -1;
int b = 150;
int c = 5;
//======================================================================================================
void main(int argc,char* argv[])
{

	if(argc == 3)
	{
		string input = argv[0];
		string inputPath = argv[1];
		string outputPath = argv[2];
		ReadInput(inputPath);
		Init();
		UpdateFitness();
		for(int i=0;i<NumberLoop;i++)
		{
			Crossover();
			UpdateFitness();
		}
		WriteOuput(outputPath);
	}
	else
	{
		printf("Tham so dong lenh sai.");
	}
}
//======================================================================================================
void ReadInput(string _InputPath)
{
	string str;
	ifstream input (_InputPath, ios::in);
	char * cStr,*p;
	int dong = 0;
	int cot = 0;
	if ( input){
		while ( !input.eof())
		{
			getline(input,str);
			cStr = new char [str.size()+1];
			strcpy (cStr, str.c_str());
			p = strtok (cStr," ");
			while (p!=NULL)
			{
				if(dong == 0)
					if(cot == 0)
					{
						a=atoi(p);
						cot++;
					}
					else if(cot == 1)
					{
						b=atoi(p);
						cot++;
					}
					else
					{
						c=atoi(p);
						dong++;
						cot = 0;
					}
				else
					if(cot == 0)
					{
						NumberLoop = atoi(p);
						cot++;
					}
					else if(cot == 1)
					{
						PopSize = atoi(p);
						cot++;
					}
					else if(cot == 2)
					{
						Pcrossover = atof(p);
						cot++;
					}
					else
						Pmultation = atof(p);
				p = strtok(NULL," ");
			}
		}//end while
		delete[] cStr;  
	}
}
//======================================================================================================
void WriteOuput(string _OutputPath)
{
	ofstream output (_OutputPath);
	output<< Result() << " ";
	output.close();
}
//======================================================================================================
//======================================================================================================
int GetRealValueFromBitString(char _BitString[])
{
	int kq = 0;
	for(int i = 0;i<8;i++)
	{
		if(_BitString[i] == '1')
		{
			kq += pow(2.0,i);
		}
	}
	return kq;
}
//======================================================================================================
NST GetNSTFromRealValue(int _RealValue)
{
	char gt[8] = {'0','0','0','0','0','0','0','0'};
	int k = 7;
	int t = _RealValue;
	while(t != 0)
	{
		gt[k--] = t%2+48;
		t /= 2;
	}
	NST kq;
	for(int i= 0;i<8;i++)
	{
		kq.BitString[i] = gt[i];
	}
	kq.RealValue = _RealValue;
	int f = -(_RealValue*_RealValue*a+_RealValue*b+c);
	kq.Fitness = MaxValue - f;
	return kq;
}
//======================================================================================================
void UpdateFitness()
{
	for(int i =0;i<PopSize;i++)
	{
		int RealValue = QuanThe[i].RealValue;
		int f = (RealValue*RealValue*a+RealValue*b+c);
		QuanThe[i].Fitness = 10000000 -(MaxValue - f);
	}
}
//======================================================================================================
void Init(void)
{
	srand(time(0));
	for(int i =0;i<PopSize;i++)
	{
		//tao trong khoang [a,b] : a + rand() % (b – a + 1)
		int realvalue = rand()%256;
		NST nst = GetNSTFromRealValue(realvalue);
		QuanThe.push_back(nst);
	}
}
//======================================================================================================
int Result()
{
	int lc = 0;
	for(int i=0;i<PopSize;i++)
		if(QuanThe[i].Fitness > QuanThe[lc].Fitness)
			lc = i;
	return QuanThe[lc].RealValue;
}
//======================================================================================================
void Crossover()
{
	Fitness_GiamDan();
	srand(time(0));
	temp.resize(0);
	int n = PopSize/10 * Pcrossover * 10;
	int bo = 0;
	int me = n-1;
	while(bo <= me)
	{
		float r = (float)rand()/(float)RAND_MAX;
		if(r<=Pcrossover)
			SubCrossover(bo,me);
		else
		{
			temp.push_back(QuanThe[bo]);
			temp.push_back(QuanThe[me]);
		}
		bo++;
		me--;
	}
	for(int i=n;i<PopSize;i++)	
		temp.push_back(QuanThe[i]);
	Update_QuanThe(temp);
}
//======================================================================================================
void Update_QuanThe(vector<NST> _temp)
{
	for(int i=0;i<PopSize;i++)
		QuanThe[i] = _temp[i];
}
//======================================================================================================
void SubCrossover(int _bo,int _me)//Đảo 1 nửa cuối: ----|====
{
	//sao chép 2 NST bố mẹ vào con
	NST con[2];
	con[0] = QuanThe[_bo];
	con[1] = QuanThe[_me];
	//2 con sau khi thừa hưởng từ lai ghép
	char gt[4];
	for(int i=0;i<4;i++)
		gt[i] = con[0].BitString[3+i];
	for(int i=0;i<4;i++)
		 con[0].BitString[3+i] = con[1].BitString[3+i];
	 con[0].RealValue = GetRealValueFromBitString(con[0].BitString);
	for(int i=0;i<4;i++)
		 con[1].BitString[3+i] = gt[i];
	con[1].RealValue = GetRealValueFromBitString(con[1].BitString);
	//đột biến 2 con
	Multation(con[0]);
	Multation(con[1]);
	
	temp.push_back(con[0]);
	temp.push_back(con[1]);

}
//======================================================================================================
void Multation(NST _NTS)
{
	//tham khảo random float http://stackoverflow.com/questions/686353/c-random-float
	float r = (float)rand()/(float)RAND_MAX;
	//kết thúc tham khảo
	if(r<=Pmultation)
	{
		SubMultation(_NTS);
	}
}
//======================================================================================================
void SubMultation(NST _NTS)//đột biến 1 điểm
{
	srand(time(0));
	int vt = rand()%9;
	_NTS.BitString[vt] = (_NTS.BitString[vt]=='0')?'1':'0';
}
//======================================================================================================
void Fitness_GiamDan()
{
	for(int i=0;i<PopSize-1;i++)
		for(int j=i+1;j<PopSize;j++)
			if(QuanThe[i].Fitness<QuanThe[j].Fitness)
			{
				NST temp = QuanThe[i];
				QuanThe[i] = QuanThe[j];
				QuanThe[j] = temp;
			}
}
//======================================================================================================